// @algorithm @lc id=236 lang=cpp 
// @title lowest-common-ancestor-of-a-binary-tree

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode * ans = NULL;
        function<bool(TreeNode*)> dfs = [&](TreeNode * node)->bool{
            if(ans || !node) return false;
            bool lc = dfs(node->left), rc = dfs(node->right);
            if((lc || rc) && (node==p || node==q) || (lc && rc)){
                ans = node;
                return true;
            }
            return node == q || node == p || lc || rc;
        };
        dfs(root);
        return ans;
    }
};